package leetcode.每日一题;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author :songyaozhang
 * @date :Created 2021/8/4 9:39
 * @description :https://leetcode-cn.com/problems/valid-triangle-number/
 */
public class 有效三角形的个数 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.triangleNumber(new int[]{2, 2, 3, 4}));

    }

    /*
    class Solution {
        public int triangleNumber(int[] nums) {
            if (nums.length < 3) return 0;
            Arrays.sort(nums);
            int count = 0;
            for (int i = 0; i < nums.length - 2; i++) {
                for (int j = i + 1; j < nums.length - 1; j++) {
                    int sum = nums[i] + nums[j];
                    //找出小于目标值得最大值
                    int index = binary_search(nums, sum, j);
                    if (index != -1) {
                        count += index - j;
                    } else break;//如果为-1，后面不需要继续了
                }
            }
            return count;
        }

        private int binary_search(int[] nums, int tar, int l) {
            int r = nums.length - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (nums[mid] < tar) {
                    l = mid;
                } else
                    r = mid - 1;
            }
            return nums[l] < tar ? l : -1;
        }
    }
     */

    class Solution {
        public int triangleNumber(int[] nums) {
            int len = nums.length;
            if (len < 3) return 0;
            Arrays.sort(nums);
            int count = 0;
            for (int i = 0; i < len - 2; i++) {
                int k = i;
                for (int j = i + 1; j < len - 1; j++) {
                    while ((k + 1) < len && nums[k + 1] < nums[i] + nums[j]) {
                        k++;
                    }
                    count += Math.max(k - j, 0);
                }
            }
            return count;
        }
    }
}
